//Given a string expression of numbers and operators, return all possible result
//s from computing all the different possible ways to group numbers and operators.
// You may return the answer in any order. 
//
// 
// Example 1: 
//
// 
//Input: expression = "2-1-1"
//Output: [0,2]
//Explanation:
//((2-1)-1) = 0 
//(2-(1-1)) = 2
// 
//
// Example 2: 
//
// 
//Input: expression = "2*3-4*5"
//Output: [-34,-14,-10,-10,10]
//Explanation:
//(2*(3-(4*5))) = -34 
//((2*3)-(4*5)) = -14 
//((2*(3-4))*5) = -10 
//(2*((3-4)*5)) = -10 
//(((2*3)-4)*5) = 10
// 
//
// 
// Constraints: 
//
// 
// 1 <= expression.length <= 20 
// expression consists of digits and the operator '+', '-', and '*'. 
// All the integer values in the input expression are in the range [0, 99]. 
// 
// Related Topics 递归 记忆化搜索 数学 字符串 动态规划 
// 👍 437 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Different Ways to Add Parentheses
class P241DifferentWaysToAddParentheses {
    public static void main(String[] args) {
        Solution solution = new P241DifferentWaysToAddParentheses().new Solution();
        // TO TEST
        System.out.println(solution.diffWaysToCompute("2*3-4*5"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> diffWaysToCompute(String expression) {
            List<Integer> list = new ArrayList<>();
            int len = expression.length();
            int start = 0;
            for (start = 0; start < len; start++) {
                if(Character.isDigit(expression.charAt(start))) continue;
                else break;
            }
            if(start==len) list.add(Integer.parseInt(expression));
            for (int i = start; i < len; i++) {
                if(Character.isDigit(expression.charAt(i))) continue;
                char op = expression.charAt(i);
                List<Integer> left = diffWaysToCompute(expression.substring(0,i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1,len));
                for (int j : left){
                    for (int k : right){
                        if(op=='+') list.add(j+k);
                        else if(op == '-') list.add(j-k);
                        else if(op == '*') list.add(j*k);
                    }
                }
            }
             return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}